package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      N对情侣坐在连续排列的2N个座位上，想要牵到对方的手。计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。
 *      一次交换可选择任意两人，让他们站起来交换座位。
 *      人和座位用0到2N-1的整数表示，情侣们按顺序编号，第一对是(0, 1)，第二对是(2, 3)，以此类推，最后一对是(2N-2, 2N-1)。
 *      这些情侣的初始座位row[i]是由最初始坐在第i个座位上的人决定的。
 *
 * 2. 算法分析
 *      题意：
 *          有N对情侣，坐在2N个座位上，但是他们之间并不是两个配对的坐着，我们的目的就是找到最少的交换次数使得最终他们之间
 *          两两牵手
 *      思路分析：
 *          1. 什么叫做情侣之间的不配对?
 *              假设当前只有一对情侣，那么他们一定是配对的，如果考虑更多对的情侣情况是怎么样的呢?
 *              1. 假设当前有两对情侣
 *                  他们之间不配对的情况只有一种，具体的例子 [0,2,1,3] (0,2) (1,3),即各自的情侣中有一个
 *                  和另外一对的其中一个坐在一起，此时只需要交换一次即可
 *
 *              2. 假设当前有三对情侣
 *                  他们之间不匹配的情况也只有一种，具体的例子[0,2,1,4,3,5] (0,2) (1,4) (3,5) 即各自的情侣中有
 *                  一个和另外一对中的其中一个坐在一起，并且构成一个环(第1对和第2对中一个配对，第2对和第3对中一个配对
 *                  第3对和第1对进行配对，只有这样，才能做到三对情侣都无法配对)，此时我们交换的次数为2次，虽然有三对
 *                  不匹配的情侣，但是只要将其中两对匹配成功之后，剩下的一对一定是匹配的，具体从上述例子分析可以看出
 *                  将第一对匹配成功：(0,1) (2,4) (3,5)
 *                  将第二对匹配成功：(0,1) (2,3) (4,5)
 *                  此时所有的情侣都已经匹配成功了，只需要两次，我们此时就可以猜测，N对不匹配的情侣之间需要交换N-1次
 *                  方可全部配对
 *
 *              3. 假设当前有N对情侣不匹配，分析同上，实际上我们可以使用数学归纳法来进行问题的分析，假设当前N-1
 *                 的情况时成立的，在考虑N，问题就划归为一个简单问题了
 *
 *         2. 对于原问题我们该如何考虑呢?
 *              现在有N对情侣坐在2N个位置上面，我们此时需要找到最少的交换次数，这N对情侣之间有些是没有配对的
 *              但是有些又是配对的，通过上述的分析，我们知道原问题被划分为若干个连通分支，最终的连通分支为N，
 *              即所有的情侣都匹配成功(此时每个最大连通分量的大小为2)，具体分析看下面的例子：
 *              [0,2,1,4,3,5,6,7,8,9,10,12,11,13]，此时图上的连通分支有(0,2,1,4,3,5) (6,7) (8,9) (10,12,11,13)
 *              我们需要考虑交换的连通图为(0,2,1,4,3,5),(10,12,11,13),交换前三对和最后两对情侣即可
 *              注意一点：上述的连通分支可以不是连续的，例如[0,5,2,3,1,4] 此时(0,5) (2,3) (1,4) 连通分支(0,5)(1,4)
 *              被(2,3) 分割开来，但是这不会影响问题的分析，问题和此没有关系，因为我们考虑的是匹配，至于在哪个座位上匹配是
 *              不重要的
 *
 *         3. 合适的算法工具：
 *              既然我们需要维护连通分量，所以我们可以使用并查集，或者使用DFS，BFS来实现连通分量的查询
 *              由于我们不需要具体找到连通分支上的元素，所以只需要采用并查集即可，找到数量就可以
 * 3. 代码实现
 *      1. 并查集的实现
 *
 *      2. DFS的实现
 *
 *      3. BFS的实现
 */
@SuppressWarnings("all")
public class Q014_情侣牵手问题 {
    /**
     * 并查集实现
     */
    class UnionFind {
        int[] root; // root数组，存放每个节点的对应的根节点
        int count; // 维护连通分量的个数
        int[] rank; // 秩数组，优化并查集的查询效率

        public UnionFind(int count) {
            this.count = count;
            root = new int[count];
            rank = new int[count];
            for(int i = 0; i < count; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        public int getCount() { // 返回连通分量的个数
            return count;
        }

        public int find(int x) { // 查询根节点
            if(root[x] == x) {
                return x;
            }
            return find(root[x]);
        }

        public void union(int x, int y) { // 合并两个跟节点
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY) {
                if(rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                }
                else if(rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                }
                else if(rank[rootX] == rank[rootY]) {
                    root[rootX] = rootY;
                    rank[rootX]++;
                }
                count--;
            }
        }
    }

    public int minSwapsCouples(int[] row) {
        int len = row.length; // 获取所有的座位数
        int N = len / 2; // 情侣对数的数量
        UnionFind uf = new UnionFind(N); // 创建并查集
        for(int i = 0; i < len; i+=2) {
            uf.union(row[i] / 2, row[i+1] / 2);
        }
        return N - uf.getCount();
    }
}
